// 要理解递归，首先要理解递归

function recursiveFunction(params) {
    recursiveFunction(params);
}

function understandRecursiveFunction(doIunderstandRecursion) {
    const recursionAnswer = confirm('Do you understand recursion?');
    if (recursionAnswer === true) {
        return true;
    }
    understandRecursiveFunction(recursionAnswer);
}

// n的阶乘 定义是n!
// 迭代阶乘
function factorialIterative(number) {
    if (number < 0) {
        return undefined
    }
    let total = 1;
    for (let n = number; n > 1; n--) {
        total = total * n
    }
    return total;
}

// 递归阶乘
// factorial(5)
// factorial(5) = 5 * factorial(4)
// factorial(5) = 5 * (4 * factorial(3))
// factorial(5) = 5 * (4 * (3 * factorial(2)))
// factorial(5) = 5 * (4 * (3 * (2 * factorial(1))))
function factorial (n) {
    debugger;
    if (n === 1 || n === 0) { // 基线条件
        return 1;
    }
    return n * factorial (n - 1) // 递归
}

// 斐波那契数列
// 0, 1, 1 , 2, 3, 5, 8, 13, 21, 34
// 位置0的斐波那契数是0
// 1 和 2 的斐波那契数是1
// n(n > 2)的斐波那契数是(n-1)的斐波那契数 + (n-2)的斐波那契数
// 迭代
function fibonacciIterative(n) {
    if (n < 1) {
        return 0;
    }
    if (n <=2 ) {
        return 1;
    }
    let fibNMinus2 = 0;
    let fibNMinus1 = 1;
    let fibN = n;
    for (let i = 2; i < n; i++) { // n >= 2
        fibN = fibNMinus1 + fibNMinus2;
        fibNMinus2 = fibNMinus1;
        fibNMinus1 = fibN;
    }
    return fibN;
}

// 递归
function fibonacci(n) {
    if (n < 1) {
        return 0
    }
    if (n <=2) {
        return 1;
    }
    return fibonacci(n -1) + fibonacci(n -2)
}

// 记忆化斐波那契数
function fibonacciMemozation(n) {
    const memo = [0, 1];
    const fibonacci = (n) => {
        if (memo[n] !== null) {
            return memo[n]
        }
        return memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    };
    return fibonacci;
}